在Binary Search tree中，我們知道我們可以在的時間內，完成Delete, find min, max, largest, smaller等操作。
下面這是一棵完美的二元樹
他的樹高為
而下面這是一棵高度為的樹，也稱為一條路徑(path)
而我們會稱第一棵完美二元搜尋樹為平衡的，而下面這一棵高度為的樹是不平衡的。
樹高的定義為找出樹根到葉節點的最長路徑長，定義完樹高之後，我們可以根樹樹高來定義這棵樹平不平衡，如果這個樹的高度為，則我們稱這棵樹是平衡的，唯有樹是平衡的，才可以保證我們上面那一些操作的效率是好的。
而在昨天，我們也提及到了節點的高度，為節點到葉節點的最長路徑長，我們也可以以一個公式來表示節點的高度
而為了使上面的公式在任何時候都可以運作，我們定義空節點的高度為-1，好處在於假設有一個葉節點，我們知道他的高度為0，則我們給他兩個空節點作為左子節點和右子節點，兩者高度皆為-1，這個假設底下，我們帶入上面的公式可以得到葉節點的高度為0。
下面將介紹一種特殊的樹，可以隨時保持在平衡的狀態，稱為平衡二元搜尋樹，為了保證他是平衡的，我們需要在每一個節點多新增一個資訊，也就是節點的高度，透過節點的高度來得知子樹的高度，從而保持平衡。
最簡單平衡樹的想法就是讓左子樹和右子樹高度一模一樣，但這件事情實際上是不可能的，會因為樹的節點個數是奇數還是偶數而導致我們無法實現這一件事情。
我們定義AVL Tree為對於每一個左子節點的高度和右子節點的高度，兩者之間的差異必須在正負1之間。
以上面這個例子來說，左邊的樹是一個AVL樹，因為左子樹的高度為3，右子樹高度為2，兩者只相差1。
而右邊這棵樹左子樹的高度為3，右子樹高度為1，兩者相差為2，不符合定義。
AVL樹的最糟糕情況會發生在每一個左子樹和右子樹之間相差的高度多餘1，我們可以使用一些方法證明這一件事情，我們假設為構成高度為
的AVL樹所需要的最少節點個數，我們可以列出遞迴式來表示
整體樹高為右子樹高度為
，左子樹高度為
，上方遞迴式由此而來。
上面這個遞迴式，看起來是曾相似... 沒錯，很像斐波那契數列，我們定義斐波那契數列為，則可以得到以下關係
，而
又可以表示成
,
，表示AVL樹的高度上界
可以發現到我們得常數十分接近1，這代表高度和節點數量的關係，更精確地來說，一棵AVL樹的高度大約為，接下來要探討插入節點的問題，當我們插入節點時，可能會破壞掉AVL樹的特性，如果特性被破壞，那麼我們必須在插入節點後，執行一些操作讓樹回復AVL樹的特性，而這種操作稱為旋轉(rotation)。
舉個例子，假設我們下方有一棵BST樹，旁邊數字表示節點的高度
我們試著插入23這個節點，並更新節點的高度
我們會發現到29, 26, 23這裡的情況十分的糟糕，且平衡樹的條件已被破壞，我們必須使用旋轉的方式進行修復
上面這個就是旋轉的操作，我們可以發現到，兩棵樹使用Inorder走訪的結果是相同的，表示都還是具備BST的性質。從左到右我們稱為k2的右旋轉，右到左稱為k1的左旋轉。
而上面那張圖，我們要做的事情就是對29這個節點進行旋轉操作
經過對29旋轉操作後，我們又可以重新得到一棵AVL樹了。
接著我們再插入55這個節點
我們會發現到，如果我們對50做右旋轉，子樹的高度會維持一樣，無法保持AVL樹的特性，而如果我們試著做左旋轉，我們會發現情況會回到我們上面插入29的情況
我們可以再做一次旋轉
而我們又可以重新得到AVL樹了，我們稱這種情況為雙旋轉(two rotations)，有可能我們有時候必須做出多於兩次的旋轉操作。
前面示範中，我們可以看到插入節點時，可能會違反AVL樹的性質，因此我們需要在插入節點後，執行一些旋轉的操作，這樣才算是完成了整個插入節點的操作，而對於不同的插入情況，我們所需要做的旋轉次數也不同，而下面將要歸納不同插入的情況。
AVL樹可以讓insert的操作保持在內，而假設一個陣列中有
個待排序的元素，則我們可以將
個元素插入到AVL樹中，然後做inorder遍歷，插入n個元素需要
的時間，inorder走訪需要
的時間，因此使用AVL樹進行排序時時間複雜度為
，和隨機化quick sort以及heap sort一樣好。
參考資料: geeksforgeeks, Introduction to algorithms 3rd, 圖片來自網路
iThome鐵人賽
看影片追技術